package study.biggestsequence;

//分治算法，返回了最大值，也返回了区间范围
public class Method3_1 {

    // 结果类，用于存储最大子数组和及其对应的区间
    public static class Result {
        double maxSum;
        int startIndex;
        int endIndex;

        Result(double maxSum, int startIndex, int endIndex) {
            this.maxSum = maxSum;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }
    }
    public static void main(String[] args) {
        double[] array = {1.5, -12.3, 3.2, -5.5, 23.2, 3.2, -1.4, -12.2, 34.2, 5.4, -7.8,1.1,-4.9};
        Result result = maxSubArraySum(array);
        System.out.println("Maximum Subarray Sum is " + result.maxSum);
        System.out.println("Start Index: " + (result.startIndex+1));
        System.out.println("End Index: " + (result.endIndex+1));

    }

    // 分治法求解最大子数组和
    public static Result maxSubArraySum(double[] nums) {
        return maxSubArraySumHelper(nums, 0, nums.length - 1);
    }

    // 辅助函数，使用分治法递归求解
    private static Result maxSubArraySumHelper(double[] nums, int left, int right) {
        // 基本情况：只有一个元素
        if (left == right) {
            return new Result(nums[left], left, right);
        }

        // 计算中间点
        int mid = (left + right) / 2;

        // 递归求解左半部分和右半部分的最大子数组和
        Result leftResult = maxSubArraySumHelper(nums, left, mid);
        Result rightResult = maxSubArraySumHelper(nums, mid + 1, right);

        // 计算跨越中间点的最大子数组和
        Result crossResult = maxCrossingSum(nums, left, mid, right);

        // 比较三者并返回最大值
        if (leftResult.maxSum >= rightResult.maxSum && leftResult.maxSum >= crossResult.maxSum) {
            return leftResult;
        } else if (rightResult.maxSum >= leftResult.maxSum && rightResult.maxSum >= crossResult.maxSum) {
            return rightResult;
        } else {
            return crossResult;
        }
    }

    // 计算跨越中间点的最大子数组和
    private static Result maxCrossingSum(double[] nums, int left, int mid, int right) {
        double sum = 0;
        double leftSum = Double.MIN_VALUE;
        int leftIndex = mid;

        // 从中间向左扫描
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
                leftIndex = i;
            }
        }

        sum = 0;
        double rightSum = Double.MIN_VALUE;
        int rightIndex = mid + 1;

        // 从中间向右扫描
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
                rightIndex = i;
            }
        }

        // 返回跨越中间点的最大子数组和
        return new Result(leftSum + rightSum, leftIndex, rightIndex);
    }
}
